import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Solution {
    //复写零
    public void DuplicateZero1(int[] num){
        int cur=0; int dest=-1;
        int n=num.length;
        while (cur<n){
            if (cur==0) dest+=2;
            else dest+=1;
            //循环停止条件
            if (dest>=n-1) break;
            cur++;
        }
        //临界情况如果dest出数组说明在最后一个位置是0的情况，第二个0写到数组外面了。
        if (dest==n){
            num[n-1]=0;
            dest-=2;
            cur--;
        }else dest--;
        //找到位置向前写
        while (cur>=0){
            if (cur==0){
                num[dest--]=0;
                num[dest--]=0;
                cur--;
            }else {
                num[dest--]=num[cur--];

            }
        }
    }


    //移动零
        public void moveZeroes(int[] nums){

            int dest=-1;   // 仓库还是空的，管理员蹲门口画圈圈
            for (int cur = 0; cur <nums.length ; cur++) {
                if (nums[cur]!=0){
                    dest++;
                    int temp=nums[cur];
                    nums[cur]=nums[dest];
                    nums[dest]=temp;
                }
            }
        }

    //快乐数
    public int bitsum(int n){
    //求平方和
        int sum=0;
        while (n!=0){
            int t=n%10;
            sum+=t*t;
            n=n/10;
        }
        return sum;
    }
    public boolean isHappy(int n) {
        int slow=n; int quick=bitsum(n);
        while (slow!=quick){
            //慢指针执行一次，快指针执行两次
            slow=bitsum(slow);
            quick=bitsum(bitsum(quick));
        }
        return slow==1;
    }
    //盛最多水的容器
    public int maxArea(int[] height) {
         int left=0;
         int right=height.length-1;
         int maxV=0;
         while (right!=left) {
             int V = (right - left) * Math.min(height[left], height[right]);
             if (V > maxV) {
                 maxV = V;
             }
             if (height[left] > height[right]) {
                 right--;
             } else {
                 left++;
             }
         }
         return maxV;
    }
 //有效三角形个数
 public int triangleNumber(int[] nums) {
     Arrays.sort(nums);
     int ret = 0;
     for (int i = nums.length - 1; i >= 2; i--) {
         int left = 0;
         int right = i - 1;
         while (left < right) {
             if (nums[left] + nums[right] > nums[i]) {
                 ret += right - left;
                 right--;
             } else {
                 left++;
             }
         }

     } return ret;
 }
 //俩数和为s
 public int[] twoSum(int[] array,int target){
        int left=0;
        int right=array.length-1;
        while (left<right){
            if (array[left]+array[right]>target){
                right--;
            }else if (array[left]+array[right]<target){
                left++;
            }else {
                return new int[]{array[left],array[right]};

        }
 }
        return new int[]{0};
}
    public List<List<Integer>> threeSum(int[] nums) {
           Arrays.sort(nums);
           List<List<Integer>> ret=new ArrayList<>();
           for (int i=0;i<nums.length-1;){
               int left=i+1;
               int right=nums.length-1;
               int t=-nums[i];

               while (left<right){
                   int sum= nums[left]+nums[right];
                   if (sum>t){
                       right--;
                   }else if (sum<t){
                       left++;
                   }else {
                      ret.add(new ArrayList<>(Arrays.asList(nums[left],nums[right],nums[i])));
                      left++;
                      right--;
                      while (left<right&&nums[left-1]==nums[right]){
                          left++;
                      }
                      while (left<right&&nums[right+1]==nums[right]){
                          right--;
                      }
                   }
               }
               i++;
               while (i<nums.length-1&&nums[i]==nums[i-1]){
                   i++;
               }
           }
           return ret;
    }
    public List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);
        int length=nums.length;
        List<List<Integer>> ret=new ArrayList<>();
        for (int i=0;i<length;){

            for (int j = i+1; j <length ; ) {
                int left=j+1;
                int right=length-1;
                long aim=(long)target-nums[i]-nums[j];
                while (left<right){
                    int sum=nums[left]+nums[right];
                    if (sum>aim){
                        right--;
                    }else if (sum<aim){
                        left++;
                    }else {
                        ret.add(new ArrayList<>(Arrays.asList(nums[i],nums[j],nums[left],nums[right])));
                        left++;
                        right--;

                        while (left<right&&nums[left]==nums[left-1]){
                            left++;
                        }
                        while (left<right&&nums[right]==nums[right+1]){
                            right--;
                        }
                    }
                }
                j++;
                while (j<length&&nums[j]==nums[j-1]){
                    j++;
                }
            }
            i++;
            while (i<length&&nums[i]==nums[i-1]){
                i++;
            }

        }
        return ret;
    }
}